home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / standards / sgml / nist / parse2b / determin.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-13  |  33.2 KB  |  741 lines
  1. /* National Institute of Standards and Technology (NIST)
  2. /* National Computer System Laboratory (NCSL)
  3. /* Office Systems Engineering (OSE) Group
  4. /* ********************************************************************
  5. /*                            D I S C L A I M E R
  6. /*                              (March 8, 1989)
  7. /*  
  8. /* There is no warranty for the NIST NCSL OSE SGML parser and/or the NIST
  9. /* NCSL OSE SGML parser validation suite.  If the SGML parser and/or
  10. /* validation suite is modified by someone else and passed on, NIST wants
  11. /* the parser's recipients to know that what they have is not what NIST
  12. /* distributed, so that any problems introduced by others will not
  13. /* reflect on our reputation.
  14. /* 
  15. /* Policies
  16. /* 
  17. /* 1. Anyone may copy and distribute verbatim copies of the SGML source
  18. /* code as received in any medium.
  19. /* 
  20. /* 2. Anyone may modify your copy or copies of SGML parser source code or
  21. /* any portion of it, and copy and distribute such modifications provided
  22. /* that all modifications are clearly associated with the entity that
  23. /* performs the modifications.
  24. /* 
  25. /* NO WARRANTY
  26. /* ===========
  27. /* 
  28. /* NIST PROVIDES ABSOLUTELY NO WARRANTY.  THE SGML PARSER AND VALIDATION
  29. /* SUITE ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
  30. /* EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  31. /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  32. /* THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS
  33. /* WITH YOU.  SHOULD THE SGML PARSER OR VALIDATION SUITE PROVE DEFECTIVE,
  34. /* YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
  35. /* 
  36. /* IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL NIST BE LIABLE FOR
  37. /* DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL,
  38. /* INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
  39. /* INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA
  40. /* BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR A
  41. /* FAILURE OF THE PROGRAM TO OPERATE WITH PROGRAMS NOT DISTRIBUTED BY
  42. /* NIST) THE PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF
  43. /* SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  44. */
  45.  
  46. /************************************************************************/
  47. /*   TITLE:          SGML PARSER                                        */
  48. /*   SYSTEM:         DTD PROCESSOR                                      */
  49. /*   SUBSYSTEM:                                                         */
  50. /*   SOURCE FILE:    DETERMIN.C                                        */
  51. /*   AUTHOR:         Michael Garris                                     */
  52. /*                                                                      */
  53. /*   DATE CREATED:                                                      */
  54. /************************************************************************/
  55. #include <stdio.h>
  56. #include "detdefs.h"
  57. #include "detglbl.h"
  58. /**************************/
  59. /* MAIN (to be removed) ***/
  60. /**************************/
  61. main(argc, argv)
  62. int argc;
  63. char *argv[];
  64. {
  65.     char eltname[128];
  66.    FILE *infile;
  67.    char inrec[2048];
  68.    int j, c, error = 0;
  69.  
  70.    if ((infile = fopen("cmfile.sgm", "r")) == NULL){
  71.      printf("unable to open cmfile.sgm \n");
  72.      exit(1);
  73.    }
  74.    while(fgets(eltname, sizeof(eltname), infile) != NULL){
  75.        fgets(inrec, sizeof(inrec), infile);
  76.       for(j = 0; j < sizeof(inrec); j++){
  77.          if (inrec[j] < ' ') {
  78.             inrec[j] = '\0';
  79.             break;
  80.          }
  81.       }
  82.       if (determin(inrec) == TRUE) {
  83.         error = 1;
  84.           printf("For element %s:", eltname);
  85.         printf("the content model:\n%s\n", inrec);
  86.         printf("is SUSPICIOUS and/or AMBIGUOUS\n");
  87.       }
  88.    }
  89.    fclose(infile);
  90.    /*(void) unlink(fname);*/
  91.    if (error != 0) {
  92.       printf("\n\nSuspicious and/or ambiguous content models were found\n");
  93.       printf("in this document - do you want to continue (Y/N)?  ");
  94.       fflush(stdout);
  95.       c = getchar();
  96.       printf("\n");
  97.       if ((c == 'y') || (c == 'Y'))
  98.          exit(0);
  99.       exit(1);
  100.    }
  101.    exit(0);
  102. }
  103.  
  104.  
  105. /******************************/
  106. /* DETERMIN *******************/
  107. /*  takes pointer to a string */
  108. /******************************/
  109. int determin(expr)
  110. char expr[];
  111. {
  112.    STATEID *stateid;   /* structure of start state pointer and */
  113.                        /*   final state pointer */
  114.    /* Preprocess the string.  First by reducing the content model
  115.         to its simplest form.  Second by tokenizing the content model
  116.         for use in determining validity of it. */
  117.    preproc(expr,buffer);  /* buffsize is the length of buffer */
  118.    ambmodel = FALSE;  /* assume valid */
  119.  
  120.    /* "endbuf" will point to the end of the expression in the buffer */
  121.    /* must send "buffer + 1" to avoid looking at the opening GRPO */
  122.  
  123.    endbuf = findendofgrp(buffer+1,1);
  124.  
  125.    /* invokes function to build FSA from expression in buffer */
  126.    /* on return, stateid will point to the FSA's start state  */
  127.    /* final state */
  128.  
  129.    stateid = proclowgrp(buffer,tokseen);
  130.  
  131.    /* invokes procedure to traverse entire FSA listing states visited */
  132.     procinordr(stateid->startptr,stateid->finalptr);  
  133.  
  134.    /* invokes procedure which traverses FSA checking for non-determinism */
  135.  
  136.    procdet(stateid->startptr ,stateid->finalptr);
  137.    free((char *)stateid);  /* will free last stateid */
  138.    freeFSA();   /* will free linked list of dynamically allocated memory */
  139.    head = NULL;
  140.  
  141.    return(ambmodel);
  142.    if (ambmodel == FALSE)
  143.        printf("Content Model is not ambiguous\n");
  144.    else 
  145.       printf("AMBIGUOUS Content Model\n");
  146. }
  147. /************************************************************************/
  148. /************************************************************************/
  149. /* PROCLOWGRP takes an expression in "buffer" and produces an equivalent*/
  150. /* FSA using a constructive algorithm.                                  */
  151. /************************************************************************/
  152. STATEID *proclowgrp(buffer,tokseen)
  153. ITEM *buffer;/* contains expression */
  154. ITEM *tokseen;/*contains tokens already FSAtokened */
  155. {
  156.    int nest;/* current level of nested parens */
  157.    ITEM *iptr = buffer;/* pointer to expression in buffer */
  158.    STATEID *stateid;/* points to start and final state of */
  159.                     /* 'intermediate' FSA */
  160.    ITEM *tokptr = tokseen;/*pointer to end of token seen list */
  161.  
  162.    /* while 'subgroups' remain in expression... */
  163.    while((nest = nestlevel(iptr)) != 0){
  164.       /* invokes procedure to point to lowest-level, leftmost, subgroup */
  165.       getlowgrp(&iptr,nest);
  166.       /* invokes procedure to process each (token,occurance indicator)   */ 
  167.       /* pair in the current subgroup, replacing them by a pointer to an */
  168.       /* equivalent 'intermediate' FSAid */
  169.       tokensingrp(iptr,tokseen,&tokptr);
  170.       /* invokes procedure to process all FSA pointers and connectors in */
  171.       /* the current subgroup, replacing the entire subgroup by a pointer*/
  172.       /* to a more complex intermediate FSAid */
  173.       lowgrp(iptr, nest);
  174.       /* reset pointer to beginning of expression in buffer and repeat the */
  175.       /* above process */
  176.       iptr = buffer;
  177.    }
  178.    /* if, once above loop is exited, the expression pointer does not point */
  179.    /* to a FSAid, then an error in the constructive algorithm has occurred */
  180.    if(iptr++->itoken != POINTER)
  181.       myexit(1,"FSA pointer id not found");
  182.    /* if constructive algorithm has completed normally, then only one FSAid*/
  183.    /* pointer remains in the expression.                                   */
  184.    stateid = iptr->ptoken;
  185.    /* return the pointer to the 'ultimate' FSAid for the*/
  186.    /* inputted expression*/
  187.    return(stateid);
  188. }
  189. /************************************************************************/
  190. /************************************************************************/
  191. /* TOKENSINGRP takes all (token,occurace indicator) pairs in a subgroup */
  192. /* and builds an equivalent FSA representing each, replacing each pair  */
  193. /* with a FSAid pointer which points to the corresponding FSA.          */
  194. /************************************************************************/
  195. void tokensingrp(iptr,tokseen,ptrin)
  196. ITEM *iptr;/* points to a token within subgroup in expression */
  197. ITEM *tokseen;/* points to head of token seen list */
  198. ITEM **ptrin;/* points to next location available in token seen list */
  199. {
  200.    int token, occind;
  201.     register int connector;
  202.    STATEID *FSAtokid;/* FSAid pointing to the start and final */
  203.                      /* state of the FSA equivalent to a */
  204.                      /* (token,occurance indicator) pair */
  205.    register ITEM *tokptr = *ptrin;
  206.    int inst;/* instance of token in token seen list */
  207.  
  208.    /* while not end of current subgroup... */
  209.    while((connector = iptr++->itoken) != GRPC){
  210.       /* skip connector, in first pass connector = GRPO */
  211.       /* if pointing to a FSAid pointer within subgroup, skip it */
  212.       /* because it has already been "FSAtokened"             */
  213.       if(iptr->itoken == POINTER){
  214. /*       commented out by Michael D. Garris on 11/23/87  */
  215. /*       due to the introduction of ITEM type            */
  216.          /* invoke procedure to skip the pointer */
  217. /*         skippointer(&iptr);       */
  218.          iptr += 2;
  219.          /* now continue and skip next connector */
  220.          continue;
  221.       }
  222.       /* invoke function to get current token from subgroup           */
  223.       /* and strip the location where the token was from the subgroup */
  224.       token = gettoken(iptr);
  225.       /* add new token to token seen list */
  226.       if (tokptr >= (tokseen + BUFFSIZE)) {
  227.         printf("overflow (tokptr) in proclowgrp()\n");
  228.         exit(0);
  229.       }
  230.       tokptr++->itoken = token;
  231.       /* search list to determine instances of token in token seen list */
  232.       inst = searchtoken(token,tokseen,tokptr);
  233.       /* invoke function to get current occurance indicator from subgoup */
  234.       /* and strip the location where the indicator was from the subgroup*/ 
  235.       occind = getoccind(iptr);
  236.       /* invoke function which takes a (token,occurance indicator) pair */
  237.       /* and build an equivalent FSA, returning the FSAid pointer */
  238.       /* pointing to the start and final state of the newly built FSA  */
  239.       FSAtokid = FSAtoken(token,inst,occind);
  240.       /* invoke procedure which inserts the FSAid pointer into the */
  241.       /* subgoup at the location where the most recently stripped */
  242.       /* token and occurance indicator had been */
  243.       insertpointer(&iptr,FSAtokid);
  244.    }
  245.    /* return from procedure after all (token,occurance indicator) pairs */
  246.    /* have been "FSAtokened"                                            */
  247.    *ptrin = tokptr;
  248. }  
  249. /************************************************************************/
  250. /************************************************************************/
  251. /* FSATOKEN inputs a (token,occurance indicator) pair and builds an     */
  252. /* builds an equivalent FSA, returning a FSAid pointer which points     */
  253. /* to the start and final state of the newly built FSA                  */
  254. /************************************************************************/
  255. STATEID *FSAtoken(token,inst,occind)
  256. int token,inst,occind;
  257. {
  258.    STATE *start,*final;/* pointers to the start state */
  259.                        /* and final state of the FSA to be built */
  260.    STATEID *startid;/* FSAid of FSA to be built */
  261.  
  262.    /* invokes function which allocates memory for a start state */
  263.    start = buildstate();
  264.    /* invokes function which allocates memory for a final state */
  265.    final = buildstate();
  266.    /* execute code according to the current occurance indicator */
  267.    switch(occind){
  268.       /* if occurance indicator is required ...*/
  269.       case REQ:
  270.          /* set start state to point to final state */
  271.          start -> lptr = final;
  272.          /* and label the edge with the token */
  273.          start -> llabel = token;
  274.          start -> linst = inst;
  275.             /****************************/
  276.             /* A1 ==>       A           */
  277.             /*         [S]----->[F]     */
  278.             /****************************/
  279.          break;
  280.       /* if occurance indicator is optional ... */
  281.       case REP:
  282.       case OPT:
  283.          /* set start state to point to final state with one edge */
  284.          start -> lptr = final;
  285.          /* and label the edge with the token */
  286.          start -> llabel = token;
  287.          start -> linst = inst;
  288.          /* also set start state to point to final state with */
  289.          /* another edge */
  290.          start -> rptr = final;
  291.          /* and label the edge with EMPTY */
  292.          start -> rlabel = EMPTY;
  293.             /****************************/
  294.             /* A? ==>       A           */
  295.             /*         [S]=====>[F]     */     
  296.             /*              e           */
  297.             /****************************/
  298.          if(occind == OPT)
  299.             break;
  300.          /* Otherwise set final state back to start state */
  301.          final->lptr = start;
  302.          final->llabel = BACK;
  303.             /****************************/
  304.             /* A? ==>       A           */
  305.             /*         [S]=====>[F]     */     
  306.             /*          ^   e    |      */
  307.             /*          |        |      */
  308.             /*          +--------+      */
  309.             /*               b          */
  310.             /****************************/
  311.       break;
  312.       /* if occurance indicator is required-repeatable... */
  313.       case PLUS:
  314.          /* set start state to point to final state */
  315.          start -> lptr = final;
  316.          /* and label the edge with the token */
  317.          start -> llabel = token;
  318.          start -> linst = inst;
  319.          /* set the final state to point to itself */
  320.          final -> lptr = final;
  321.          /* and label the edge with the token */
  322.          final -> llabel = token;
  323.          final -> linst = inst;
  324.             /****************************/
  325.             /* A+ ==>       A           */
  326.             /*         [S]----->[F]-+   */     
  327.             /*                  ^   |A  */ 
  328.             /*                  |___|   */
  329.             /****************************/
  330.          break;
  331.    }
  332.    /* invoke function which allocates memory for a FSAid */
  333.    startid = buildid();
  334.    /* set "startid" to point to the start state of the FSA just built */
  335.    startid -> startptr = start;
  336.    /* set "startid" to point to the final state of the FSA just built */
  337.    startid -> finalptr = final;
  338.          /****************************/
  339.          /*  [ID]--->[S]- ... ->[F]  */     
  340.          /*    |                 ^   */
  341.          /*    |_________________|   */ 
  342.          /****************************/
  343.    /* return the pointer to the FSAid of the FSA just built */
  344.    return(startid);
  345. }
  346. /************************************************************************/
  347. /************************************************************************/
  348. /* LOWGRP inputs a subgroup of an expression whose tokens have pre-     */
  349. /* viously been "FSAtokened" and processes these FSAtokens with their   */
  350. /* connectors, building an FSA equivalent to the "content" of the       */
  351. /* current subgroup.  This procedure then passes this "subgroup"FSA     */
  352. /* along with the occurance indicator on the subgroup to another process*/
  353. /* which builds an FSA equivalent to the "entire" subgroup, repalcing   */
  354. /* the subgroup with an FSAid pointer pointing to the newly built ,more */
  355. /* complex, FSA.                                                        */
  356. /************************************************************************/
  357. void lowgrp(iptr, nest)
  358. ITEM *iptr;
  359. int nest;
  360. {
  361.    int connector,occindongrp;
  362.    STATEID *FSAid;/* the "ultimate" FSAid for the subgroup */
  363.    STATEID *FSAtokid;/* the FSAtokens from the subgroup being */
  364.                      /* added to the "ultimate" FSAid for the subgroup */
  365.  
  366.    /* invokes procedure which will strip the GRPO from the subgroup */
  367.    stripunit(INT,iptr);
  368.    /* invokes function which allocates memory for a FSAid */
  369.    FSAid = buildid();
  370.    /* invokes a function to get and strip current /*
  371.    /* FSAtoken from the subgroup */
  372.    FSAtokid = getFSAtoken(iptr);
  373.    /* for the first FSAtoken stripped from the subgroup, */
  374.    /* simply set the "ultimate" FSAid to point to it.    */
  375.    /* set FSAid to point to the first FSAtoken's start state */
  376.    FSAid -> startptr = FSAtokid -> startptr;
  377.    /* and set FSAid to plint to the first FSAtoken's final state */
  378.    FSAid -> finalptr = FSAtokid -> finalptr;
  379.    free((char *)FSAtokid);   
  380.    /* while not end of subgroup... */
  381.    while((connector = getconnector(iptr)) != GRPC){
  382.       /* invokes a function to get and strip current connector from subgroup */
  383.       /* invokes a function to get and strip next FSAtoken from subgroup */
  384.       FSAtokid = getFSAtoken(iptr);
  385.       /* invokes a function to build a new "ultimate" FSAid, returning */
  386.       /* a FSAid pointer pointing to the newly built "unltimate" FSA. */
  387.       FSAid = FSAgrp(FSAid,connector,FSAtokid);
  388.    }
  389.    /* if level of nesting > 1, then the occurance indicator along with */
  390.    /* the "ultimate" FSA just built for the current subgroup must be   */
  391.    /* processed                                                        */
  392. /* INTERESTING */
  393.    if(nest >= 1){
  394.       /* invokes a function to get and strip the occurance indicator off */
  395.       /* of the current subgroup                                         */
  396.       occindongrp = getoccind(iptr);
  397.       /* invokes a function taking the "ultimate" FSA and the occurance */
  398.       /* indicator from the current subgroup and building an equivalent */
  399.       /* new ultimate FSA for the "entire" subgroup, returning the FSAid*/
  400.       /* pointer pointing to the new, more complex, FSA                 */
  401.       FSAid = FSAgrpocid(FSAid,occindongrp);
  402.    }
  403.    /* invoke a procedure to insert the newly built "ultimate" FSAid */
  404.    /* pointer into the expression where the current subgroup was located*/
  405.    insertpointer(&iptr,FSAid);
  406.    /* exit this procedure after entire subgroup has been processed and */
  407.    /* replaced by an equivalent FSAid pointer                          */
  408. }  
  409. /************************************************************************/
  410. /************************************************************************/
  411. /* GETFSATOKEN gets the FSAtoken pointed to by "iptr", strips the space */
  412. /* taken by the FSAtoken from the expression, and returns the FSAtoken  */ 
  413. /************************************************************************/
  414. STATEID *getFSAtoken(iptr)
  415. ITEM *iptr;
  416. {
  417.    STATEID *stateid;/* will contain the FSAtoken */
  418.  
  419.    /* if "iptr" does not point to a FSAid, then execution error */
  420.    /* in constructive algorithm                                 */
  421.    if(iptr->itoken != POINTER)
  422.       myexit(1,"FSA token id ponter not found");
  423.    /* invoke procedure to strip the, -1, signalling a pointer */
  424.    /* from the expression at "iptr"                           */
  425.    stripunit(INT,iptr);
  426.    /* set "stateid" to the current FSAtoken pointed to */
  427.    stateid = iptr->ptoken;
  428.    /* invoke procedure to strip the current FSAtoken from the expression */
  429.    stripunit(PTR,iptr);
  430.    /* return "stateid" which was assigned FSAtoken */
  431.    return(stateid);
  432. }
  433. /************************************************************************/
  434. /************************************************************************/
  435. /* FSAGRP inputs the most recent "ultimate" FSAid and (connector,FSAid) */
  436. /* pair, building a new, more complex, "ultimate" FSA, returning the    */
  437. /* FSAid pointing to the "new" ultimate FSA.                            */
  438. /************************************************************************/
  439. STATEID *FSAgrp(FSAid,connector,FSAtokid)
  440. STATEID *FSAid,*FSAtokid;
  441. int connector;
  442. {
  443.    STATE *newstart, *newfinal;/* new start and final states */
  444.                               /* of new "ultimate" FSA being built */
  445.    STATEID *newstartid;/* new FSAid to point to FSA being built */
  446.  
  447.    switch(connector){
  448.       /* if connector is the sequence operator ... */
  449.       case SEQ:
  450.          /* if the "ultimate" FSA's final state's left pointer is NULL ...*/
  451.          if((FSAid->finalptr->lptr) == NULL){
  452.             /* then the left pointer is set to point to the start */
  453.             /* state of the FSAtokid */
  454.             FSAid->finalptr->lptr = FSAtokid -> startptr;
  455.             /* and the edge is marked EMPTY */
  456.             FSAid->finalptr->llabel = EMPTY;
  457.          }
  458.          /* otherwise the left pointer of the "ultimate" FSA's final state */
  459.          /* is assigned to something valid */
  460.          else{
  461.             /* so check the right pointer of the "ultimate FSA's final */
  462.             /* and if not NULL ... */
  463.             if((FSAid->finalptr->rptr) == NULL){
  464.                /* then the right pointer is set to point to the start */
  465.                /* state of the FSAtokid */
  466.                FSAid->finalptr->rptr = FSAtokid -> startptr;
  467.                /* and the edge is marked EMPTY */
  468.                FSAid->finalptr->rlabel = EMPTY;
  469.             }
  470.             /* otherwise the final state of the "utimate" FSA is full */
  471.             /* which means an error occurred in the constructive algorithm */
  472.             else
  473.                myexit(1,"no null ptr found in state");
  474.          }
  475.             /*********************************/
  476.             /* [FSAid]---->[S]- ... ->[F]--+ */
  477.             /*    |                    ^   | */
  478.             /*    |____________________|  e| */
  479.             /*                 +-----------+ */
  480.             /*                 |             */
  481.             /*                 V             */
  482.             /* [FSAtokid]---->[S]- ... ->[F] */
  483.             /*    |                       ^  */
  484.             /*    |_______________________|  */
  485.             /*********************************/
  486.  
  487.          /* set the "ultimate" FSAid to point to the finalstate of */
  488.          /* the FSAtokid */
  489.          FSAid->finalptr = FSAtokid->finalptr;
  490.          /* release the memory of the FSAtokid */
  491.          free((char *)FSAtokid);
  492.             /***********************************/
  493.             /* [FSAid]---->[S]- ... ->[F]--+   */
  494.             /*    |                        |   */
  495.             /*    |                   e    |   */
  496.             /* +--+              +---------+   */
  497.             /* |                 |             */
  498.             /* |                 V             */
  499.             /* | [FSAtokid]-||  [S]- ... ->[F] */
  500.             /* |    |                       ^  */
  501.             /* |    =                       |  */
  502.             /* +----------------------------+  */
  503.             /***********************************/
  504.          /* return the "new" ultimate FSAid */
  505.          return(FSAid);
  506.       /* if connector is the OR operator ...*/
  507.       case OR:
  508.          /* allocate memory for a new start state */
  509.          newstart = buildstate();
  510.          /* allocate memory for a new final state */
  511.          newfinal = buildstate();
  512.          /* allocate memory for a new FSAid */
  513.          newstartid = buildid();
  514.          /* set new FSAid to point to new start state */
  515.          newstartid->startptr = newstart;
  516.          /* set new FSAid to point to new final state */
  517.          newstartid->finalptr = newfinal;
  518.          /* set new start state to point to start state of "ultimate" FSA */
  519.          newstart->lptr = FSAid->startptr;
  520.          /* mark the edge EMPTY */
  521.          newstart->llabel = EMPTY;
  522.          /* set new start state to point to start state of FSAtokid */
  523.          newstart->rptr = FSAtokid->startptr;
  524.          /* mark the edge EMPTY */
  525.          newstart->rlabel = EMPTY;
  526.       /*************************************************************/
  527.       /*                            +---------------+              */
  528.       /*                            |               |              */
  529.       /*                            |               V              */
  530.       /*                           e|  [FSAid]---->[S]- ... ->[F]  */
  531.       /*                            |     |                    ^   */
  532.       /*                            |     |____________________|   */
  533.       /* [newstartid]--->[newstart]=+----------------+             */
  534.       /*           |                      e          |             */
  535.       /*           |                                 V             */
  536.       /*           V                 [FSAtokid]---->[S]- ... ->[F] */
  537.       /*         [newfinal]             |                       ^  */
  538.       /*                                |_______________________|  */
  539.       /*************************************************************/
  540.          /* if left pointer of "ultimate" FSA's final state is NULL ..*/
  541.          if((FSAid->finalptr->lptr) == NULL){
  542.             /* set FSAid to point to the new final state */
  543.             FSAid->finalptr->lptr = newfinal;
  544.             /* and mark the edge as EMPTY */
  545.             FSAid->finalptr->llabel = EMPTY;
  546.          }
  547.          /* otherwise the left pointer of the "ultimate" FSA's final state */
  548.          /* is assigned valid data */
  549.          else{
  550.             /* if right pointer of "ultimate" FSA's final state is NULL ..*/
  551.             if((FSAid->finalptr->rptr) == NULL){
  552.                /* set FSAid to point to the new final state */
  553.                FSAid->finalptr->rptr = newfinal;
  554.                /* and mark the edge as EMPTY */
  555.                FSAid->finalptr->rlabel = EMPTY;
  556.             }
  557.             else
  558.                /* otherwise the final state of "ultimate" FSA is full */
  559.                /* implying that an error has occurred in the constructive */
  560.                /* algotithm */
  561.                myexit(1,"no null ptr found in state");
  562.          }
  563.         /* if left pointer of FSAtokid's final state pointer is NULL ...*/ 
  564.         if((FSAtokid->finalptr->lptr) == NULL){
  565.             /* set FSAtoken's final state to the new final state */
  566.             FSAtokid->finalptr->lptr = newfinal;
  567.             /* and mark the edge as EMPTY */
  568.             FSAtokid->finalptr->llabel = EMPTY;
  569.          }
  570.          /* otherwise the left pointer is already assigned */
  571.          else{
  572.             /* if right pointer of FSAtokid's final state pointer is NULL ...*/
  573.             if((FSAtokid->finalptr->rptr) == NULL){
  574.                /* set FSAtoken's final state to the new final state */
  575.                FSAtokid->finalptr->rptr = newfinal;
  576.                /* and mark the edge as EMPTY */
  577.                FSAtokid->finalptr->rlabel = EMPTY;
  578.             }
  579.             else
  580.                /* otherwise FSAtokid's final state is full implying an */
  581.                /* error has occurred in the constructive algorithm */
  582.                myexit(1,"no null ptr found in state");
  583.          }
  584.          /* release the memory of the  "old" ultimate FSAid */
  585.          free((char *)FSAid);  /* we took cast out */
  586.          /* release the memory of the FSAtoken's id */
  587.          free((char *)FSAtokid); /* we took cast out */
  588.    /*********************************************************************/
  589.    /*                     +-----------------+                           */
  590.    /* [newstartid]        |                 |                           */
  591.    /*     |   |           |                 V                           */
  592.    /*     |   |          e|    [FSAid]-||  [S]- ... ->[F]---+           */
  593.    /*     |   |           |       |                         |e          */
  594.    /*     |   |           |       =                         V           */
  595.    /*     |   +->[newstart]                                 [newfinal]  */
  596.    /*     |               |     =                           ^   ^       */
  597.    /*     |              e|     |                           |e  |       */
  598.    /*     |               |   [FSAtokid]-||  [S]- ... ->[F]-+   |       */
  599.    /*     |               |                   ^                 |       */
  600.    /*     |               |___________________|                 |       */
  601.    /*     |_____________________________________________________|       */
  602.    /*********************************************************************/
  603.          /* return newstartid to become the new "ultimate" FSAid */
  604.          return(newstartid);
  605.    }
  606.    return(0);
  607. }        
  608. /************************************************************************/
  609. /************************************************************************/
  610. /* FSAGRPOCID inputs an equivalent FSA of a subgroup and the occurance  */
  611. /* indicator on that group and forms a new FSA for that "entire" sub-   */
  612. /* group, returning a FSAid for the new, more complex, FSA.             */
  613. /************************************************************************/
  614. STATEID *FSAgrpocid(FSAid,occindongrp)
  615. STATEID *FSAid;
  616. int occindongrp;
  617. {
  618.    STATEID *newstartid;/* new FSAid, to be used if, optional, */
  619.                        /* occurance indicator */
  620.    STATE *newstart;/* new start state for FSA being built */
  621.                    /* if occurance indicator is ,optional */
  622.  
  623.    STATE *newfinal;/* new final state for FSA being built */
  624.                    /* if occurance indicator is required/repeatable */
  625.  
  626.    switch(occindongrp){
  627.       /* if occurance indicator on the group is required ...*/
  628.       case(REQ):
  629.          /* simply return, no changes to current FSA is needed */
  630.          return(FSAid);
  631.       /* if occurance indicator on the group is required-repeatable ...*/
  632.       case(PLUS):
  633.          /* allocate new final state if plus */
  634.          newfinal = buildstate();
  635.          /* set newfinal to point to FSA's start state */
  636.          newfinal->lptr = FSAid->startptr;
  637.          /* and mark the edge as BACK */
  638.          newfinal->llabel = BACK;
  639.          /* if the FSA's final state's left pointer is NULL ...*/
  640.          if((FSAid->finalptr->lptr) == NULL){
  641.             /* set FSA's final state to point to new final state */
  642.             FSAid->finalptr->lptr = newfinal;
  643.             /* and mark the edge as EMPTY */
  644.             FSAid->finalptr->llabel = EMPTY;
  645.             /* update FSAid's finalptr to point to new final state */
  646.             FSAid->finalptr = newfinal;
  647.          }
  648.          /* otherwise the left pointer of the final state has already */
  649.          /* been assigned */
  650.          else{
  651.             /* if the FSA's final state's right pointer is NULL ...*/
  652.             if((FSAid->finalptr->rptr) == NULL){
  653.                /* set FSA's final state to point to new final state */
  654.                FSAid->finalptr->rptr = newfinal;
  655.                /* and mark the edge as EMPTY */
  656.                FSAid->finalptr->rlabel = EMPTY;
  657.                /* update FSAid's finalptr to point to new final state */
  658.                FSAid->finalptr = newfinal;
  659.             }
  660.             else
  661.                /* otherwise an error has occurred in the constructive */
  662.                /* algorithm because the final state is full */
  663.                myexit(1,"no null ptr found in state");
  664.          }
  665.             /*******************************/
  666.             /*               __________    */
  667.             /*              |    b     |   */
  668.             /*              V          |   */
  669.             /*  [FSAid]--->[S]- ... ->[F]  */     
  670.             /*      |                  ^   */
  671.             /*      |__________________|   */ 
  672.             /*******************************/
  673.          /* return the FSAid of the old FSA as the new FSAid */
  674.          return(FSAid);
  675.       /* if occurance indicator on the group is optional .. */
  676.       case(REP):
  677.       case(OPT):
  678.          /* allocate memory for a new FSAid */
  679.          newstartid = buildid();
  680.          /* allocate memory for a new start state */
  681.          newstart = buildstate();
  682.          /* allocate memory for a new final state */
  683.          newfinal = buildstate();
  684.          /* set the new FSAid to point to the new start state */
  685.          newstartid->startptr = newstart;
  686.  
  687.          /* set the new FSAid to point to the new final state */
  688.          newstartid->finalptr = newfinal;
  689.  
  690.          /* set the new start state to point to the start state of the */
  691.          /* current FSA */
  692.          newstart->lptr = FSAid->startptr;
  693.          /* and mark the edge as EMPTY */
  694.          newstart->llabel = EMPTY;
  695.  
  696.          /* set the new start state to point to the new final state */
  697.          newstart->rptr = newfinal;
  698.          newstart->rlabel = EMPTY;
  699.  
  700.          /* set old final state to point to the new final state */
  701.          if(FSAid->finalptr->lptr == NULL){
  702.             FSAid->finalptr->lptr = newfinal;
  703.             /* set old final state's left pointer to EMPTY */
  704.             FSAid->finalptr->llabel = EMPTY;
  705.          }
  706.          else{
  707.             if(FSAid->finalptr->rptr == NULL){
  708.                FSAid->finalptr->rptr = newfinal;
  709.                FSAid->finalptr->rlabel = EMPTY;
  710.             }
  711.             else{
  712.                fprintf(stderr,"State pointer overflow occurred\n");
  713.                exit(1);
  714.             }
  715.          }         
  716.          /* release the memory of the old FSAid */
  717.          free((char *)FSAid); /* we took cast out */
  718.  
  719.             /*******************************************************/
  720.             /*                      +---------------+              */
  721.             /* [newstartid]        e|               |              */
  722.             /*     |  |             |               V              */
  723.             /*     |  +--->[newstart]  [FSAid]-||  [S]- ... ->[F]  */     
  724.             /*     |                |         |               ^ ^  */
  725.             /*     |               e|         =               | |  */ 
  726.             /*     |                +-------------------------+ |  */
  727.             /*     |____________________________________________|  */
  728.             /*******************************************************/
  729.          /* return the new FSAid to replace the old FSAid */
  730.          if(occindongrp == OPT)
  731.             return(newstartid);
  732.          /* Otherwise set newfinal state to point to new start state */
  733.          newfinal->lptr = newstart;
  734.          newfinal->llabel = BACK;
  735.          return(newstartid);
  736.    }
  737.    /* code should never be reached, but if so, then an error in */
  738.    /* the constructive algorithm */
  739.    return(0);
  740. }
  741.